#include <MSTTask.h>

/**
 * MSTTask_t implementation
 */

// default constructor
MSTTask_t::MSTTask_t() {
  graph   = NULL;
  Q       = NULL;
  e_map   = new std::map <edge_descriptor_t, int>();
  v_map   = new std::map <int, int>();
  who_map = new std::map <vertex_iterator_t, vertex_iterator_t>();
  v_queue = new std::queue <vertex_iterator_t>();
  count = 0;
  initial = true;

  // initialize mutex
  pthread_mutex_init(&vmutex, NULL);
  pthread_mutex_init(&emutex, NULL);
  pthread_mutex_init(&cmutex, NULL);
  pthread_mutex_init(&qmutex, NULL);
  pthread_mutex_init(&who_mutex, NULL);
}

// constructor
MSTTask_t::MSTTask_t(Graph_t * _graph, WorkQueue *  _Q) {
  graph   = _graph;
  Q       = _Q;
  e_map   = new std::map <edge_descriptor_t, int>();
  v_map   = new std::map <int, int>();
  who_map = new std::map <vertex_iterator_t, vertex_iterator_t>();
  v_queue = new std::queue <vertex_iterator_t>();
  initial = true;
  count = 0;

  // initialize maps to default values
  vertex_iterator_t v, vend;
  for (tie(v, vend) = vertices(*graph) ;  v != vend ; v++) {
    (*v_map)[*v] = 0; // not in tree
  }

  edge_iterator_t e, eend;
  for (tie(e, eend) = edges(*graph) ; e != eend ; e++) {
    (*e_map)[*e] = 0; // not in tree
  }

  // initialize mutex
  pthread_mutex_init(&vmutex, NULL);
  pthread_mutex_init(&emutex, NULL);
  pthread_mutex_init(&cmutex, NULL);
  pthread_mutex_init(&qmutex, NULL);
  pthread_mutex_init(&who_mutex, NULL);
}

// destructor
MSTTask_t::~MSTTask_t() {
  graph   = NULL;
  Q       = NULL;
  initial = false;
  
  delete e_map;
  delete v_map;
  delete who_map;
  delete v_queue;

  pthread_mutex_destroy(&vmutex);
  pthread_mutex_destroy(&cmutex);
  pthread_mutex_destroy(&emutex);
  pthread_mutex_destroy(&qmutex);
  pthread_mutex_destroy(&who_mutex);  
}

// run method 
void MSTTask_t::run() {
  // everything in initialized to default values
  // start from root and put all out edges and vertices in tree
  if (initial) {
    gettimeofday(&tim, NULL);
    t1=tim.tv_sec+(tim.tv_usec/1000000.0);	
    int root_id = 0;
    (*v_map)[root_id] = 1; // root visited
    (*who_map)[root_id] = -1;
    out_edge_iterator_t e, eend;
    for (tie(e, eend) = out_edges(0, *graph) ; e != eend ; e++) {
      // add edges to tree
      (*e_map)[*e] = 1;
      // add subvertices to map
      (*v_map)[target(*e, *graph)] = 1;
      // fix parent
      (*who_map)[target(*e, *graph)] = root_id;
      // add vertices to be done queue
      v_queue->push(target(*e, *graph));
    }
    initial = false;
  }

  // now for each vertex in queue start the algorithm
  pthread_mutex_lock(&cmutex); // acquire count mutex
  if (count == 0) {
    pthread_mutex_unlock(&cmutex);
    pthread_mutex_lock(&qmutex);
    if (v_queue->empty()) { // now done 
      pthread_mutex_unlock(&qmutex);
      *doneState = Done; // indicate to TFrame that task is done 
      std::map<vertex_iterator_t, vertex_iterator_t>::iterator it;
      for (it = who_map->begin() ; it != who_map->end() ; it++) {
           std::cout << "From " << *((*it).first) << " to " << *((*it).second) << std::endl;
      }
    } else { // actual work here
      // unlock mutex on queue
      // Go over vertices in the queue and create tasks
      vertex_iterator_t it;
      for (int i = 0; i < v_queue->size() ; i++) {
	// get the front element in the queue
	it = v_queue->front();
	// pop the queue 
	v_queue->pop();
	// create a new task 
	MergeTask_t * mymerge = new MergeTask_t(graph, it, &count, e_map, v_map, who_map, v_queue, &qmutex, &cmutex, &emutex, &vmutex, &who_mutex);
	// acquire lock on count
	pthread_mutex_lock(&cmutex);
	// increment count
	count++;
	// release lock on count
	pthread_mutex_unlock(&cmutex);
	// add task to queue
	Q->addTask(mymerge);
      }
      // unlock mutex on queue
      pthread_mutex_unlock(&qmutex);
    }
  } else {
    pthread_mutex_unlock(&cmutex); // release count mutex
    *doneState = Working; // still working, put me back in work queue
  }
}



/*********************************************************************************************/
/************************************* MERGE TASK ********************************************/
/*********************************************************************************************/

// default constructor
MergeTask_t::MergeTask_t() {
  // initialize all to null
  graph     = NULL;
  e_map     = NULL;
  v_map     = NULL;
  who_map   = NULL;
  v_queue   = NULL;

  qmutex    = NULL;
  cmutex    = NULL;
  emutex    = NULL;
  vmutex    = NULL;
  who_mutex = NULL;
}

// constructor
MergeTask_t::MergeTask_t(Graph_t * _graph,
			 vertex_iterator_t _vit, 
			 int * _count,
			 std::map<edge_descriptor_t, int> * _e_map,
			 std::map<int, int> * _v_map,
			 std::map<vertex_iterator_t, vertex_iterator_t> * _who_map,
			 std::queue<vertex_iterator_t> * _v_queue,
			 pthread_mutex_t * _qmutex, 
			 pthread_mutex_t * _cmutex, 
			 pthread_mutex_t * _emutex,  
			 pthread_mutex_t * _vmutex, 
			 pthread_mutex_t * _who_mutex
			 ) {
  graph     = _graph;
  vit       = _vit;
  count     = _count;
  
  e_map     = _e_map;
  v_map     = _v_map;
  who_map   = _who_map;
  v_queue   = _v_queue;
  
  qmutex    = _qmutex;
  cmutex    = _cmutex;
  emutex    = _emutex;
  vmutex    = _vmutex;
  who_mutex = _who_mutex;
}

// destructor 
MergeTask_t::~MergeTask_t() {
  graph = NULL;
  count = NULL;
  qmutex = NULL;
  cmutex = NULL;
  emutex = NULL;
  vmutex = NULL;
  who_mutex = NULL;
}

// run method
void MergeTask_t::run() {
  out_edge_iterator_t e, eend;
  for (tie(e,eend) = out_edges(*vit, *graph) ; e != eend; e++) {
    // get target id
    int target_id = target(*e, *graph);
    // check if vertex is in the tree
    pthread_mutex_lock(vmutex); // lock mutex on vertices
    if ((*v_map)[target_id] == 0) { // not visited
      (*v_map)[target_id] = 1; // mark it as visited
      // release lock
      pthread_mutex_unlock(vmutex);
      // add edge to list also
      pthread_mutex_lock(emutex);
      (*e_map)[*e] = 1; // mark as in the tree
      pthread_mutex_unlock(emutex);
      // add parent
      pthread_mutex_lock(who_mutex);
      (*who_map)[target_id] = vit;
      pthread_mutex_unlock(who_mutex);
      // add to queue
      pthread_mutex_lock(qmutex);
      v_queue->push(target_id);
      pthread_mutex_unlock(qmutex);
    } else { // already in tree must check for weigths
      pthread_mutex_unlock(vmutex);
      weightmap_t weightmap; // get map of weights
      pthread_mutex_lock(who_mutex);
      if ((*who_map)[target_id] != vit) { // I'm not the parent of this 
	// check and compare weights
	edge_descriptor_t desc; bool cond;
	int parent_id = *((*who_map)[target_id]);
	if (parent_id != -1) {
	  tie(desc, cond) = edge(target_id, parent_id, *graph);
	  if (weightmap[desc] > weightmap[*e]) {// should replace now 
	    (*who_map)[target_id] = vit;
	    pthread_mutex_unlock(who_mutex);
	    // remove old edge from tree and insert new edge
	    pthread_mutex_lock(emutex);
	    (*e_map)[desc] = 0; // no longer in tree
	    (*e_map)[*e] = 1; // add new edge to tree
	    pthread_mutex_unlock(emutex);
	  } else { // do nothing 
	    pthread_mutex_unlock(who_mutex);
	  }
	} else {
	  pthread_mutex_unlock(who_mutex);
	}
      } else {
	pthread_mutex_unlock(who_mutex);
      }
    }
  }
  pthread_mutex_lock(cmutex);
  (*count)--;
  pthread_mutex_unlock(cmutex);
  *doneState = Done;
}
